#include <poll.h>
#include <stdio.h>
#include <netdb.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
#include <sys/socket.h>

#define BUFFERSIZE 255
#define MAXENTRIES 10000
#define MUTATIONRATE 5

int numPins;
int numColors;
int sockfd;

// structure for a linked list
typedef struct colornode{
	char color[21];
	struct colornode* next;
	struct colornode* previous;
}ColorNode;

//structure for guessed entries
typedef struct entry{
	int *code;
	int whites;
	int reds;
	struct entry* next;
	struct entry* previous;
}Entry;

int totalEntries = 0;
int guesses = 0;

ColorNode *colorList=NULL;
Entry *primaryEntry=NULL;
Entry *lastEntry=NULL;

void initialize(char* host, char* port){
	struct sockaddr_in serv_addr;
	struct hostent *server;
	int n, rv;
	int len=0;
	int index=0;
	char buffer[BUFFERSIZE+1];
	char color[21];
	char previous[21]="";
	ColorNode *colorInsert=NULL;
	ColorNode *newColor=NULL;
	struct pollfd ufds;
	
	bzero(previous, 21);
	server = gethostbyname(host);
	sockfd = socket(AF_INET, SOCK_STREAM, 0);
	bzero((char *) &serv_addr, sizeof(serv_addr));
	serv_addr.sin_family = AF_INET;
	serv_addr.sin_port = htons(atoi(port));
	bcopy((char *)server->h_addr,
		  (char *)&serv_addr.sin_addr.s_addr,
		  server->h_length);
	if(connect(sockfd,(struct sockaddr *) &serv_addr,sizeof(serv_addr)) < 0){
		exit(1);
	}
	n=read(sockfd,buffer,BUFFERSIZE);
	numPins=atoi(buffer);
	numColors=0;
	while(buffer[index]!=';' && index<n){
		index++;
	}
	index++;
	while(n>0){
		while(index+len<n){
			len++;
			if(buffer[index+len]==','){
				newColor=(ColorNode*) malloc(sizeof(ColorNode));
				strncat(previous, &(buffer[index]), len);
				strcpy(newColor->color, previous);
				strcpy(previous, "");
				if(colorList==NULL){
					newColor->previous=NULL;
					colorList=newColor;
				}
				else{
					colorInsert->next=newColor;
					newColor->previous=colorInsert;
				}
				newColor->next=NULL;
				colorInsert=newColor;
				numColors++;
				index=index+len+1;
				len=0;
			}
		}
		strncat(previous, &(buffer[index]), len);
		previous[len]='\0';
		
		ufds.fd = sockfd;
		ufds.events = POLLIN;
		rv = poll(&ufds, 1, 1000);
		if(rv>0){
			n=read(sockfd,buffer,BUFFERSIZE);
		}
		else{
			n=0;
		}
		index=0;
		len=0;
	}
	newColor=(ColorNode*) malloc(sizeof(ColorNode));
	strncpy(newColor->color, previous, strlen(previous)-1);
	if(colorList==NULL){
		newColor->previous=NULL;
		colorList=newColor;
	}
	else{
		colorInsert->next=newColor;
		newColor->previous=colorInsert;
	}
	newColor->next=NULL;
	numColors++;
}

//checks to see if a code was guessed
//pointers probably need to be checked

int findEntry(int *code){
	Entry *search = primaryEntry;
	int found = 0;
	int i;
	while(search != NULL && found != 1){
		found = 1;
		for(i = 0; i < numPins; i++){
			if(code[i] != search->code[i]){
				found = 0;
				break;
			}
		}
		search = search->next;
	}
	return found;
}

void addEntry(int *code, int whites, int reds){
	Entry *newEntry = (Entry*) malloc(sizeof(Entry));
	Entry *temp = primaryEntry;
	Entry *previous = NULL;
	int inserted = 0;
	int index = 0;
	int i;
	
	newEntry->code = (int*)malloc(sizeof(int)*numPins);
	for(i=0; i<numPins; i++){
		newEntry->code[i] = code[i];
	}
	newEntry->whites = whites;
	newEntry->reds = reds;
	newEntry->previous=NULL;
	newEntry->next=NULL;
	int newPegs = whites + reds;
	if(primaryEntry == NULL){
		primaryEntry = newEntry;
		lastEntry = newEntry;
	}
	else{
		while(temp != NULL && inserted == 0){
			int tempPegs = temp->reds + temp->whites;
			if(tempPegs < newPegs || index > MAXENTRIES / 4){
				newEntry->previous = previous;
				newEntry->next = temp;
				temp->previous = newEntry;
				if(previous == NULL){
					primaryEntry = newEntry;
				}
				else{
					previous->next = newEntry;
				}
				inserted = 1;
			}
			else if(tempPegs = newPegs){
				if(newEntry->reds > temp->reds){
					newEntry->previous = previous;
					newEntry->next = temp;
					temp->previous = newEntry;
					if(previous == NULL){
						primaryEntry = newEntry;
					}
					else{
						previous->next = newEntry;
					}
					inserted = 1;
				}
				else{
					previous = temp;
					temp=temp->next;
					index++;
				}
			}
			else{
				previous = temp;
				temp = temp->next;
				index++;
			}
			
		}
		if(inserted == 0){
			previous->next = newEntry;
			newEntry->previous = previous;
			lastEntry = newEntry;
		}
	}
	totalEntries++;
	if(totalEntries > MAXENTRIES){
		lastEntry=lastEntry->previous;
		free(lastEntry->next);
		lastEntry->next=NULL;
		totalEntries--;
	}
	if(reds==numPins){
		printf("found the solution in %d guesses\n",guesses);
		printf("solution: %d",code[0]);
		for(i=1; i<numPins; i++){
			printf(",%d",code[i]);
		}
		printf("\n");
		exit(0);
	}
}

void submitGuess(int code[], int* whites, int*reds){
	char submission[numPins*21];
	char buffer[BUFFERSIZE+1];
	int index=0;
	int i, j, len;
	ColorNode *temp;
	
	for(i=0; i<numPins; i++){
		temp=colorList;
		j=0;
		if(code[i]>numColors || code[i]<0){
			printf("invalid color index: %d\n",code[i]);
			exit(0);
		}
		while(j<code[i]){
			if(temp!=NULL){
				temp=temp->next;
			}
			j++;
		}
		if(i>0){
			strcat(&(submission[index]), ",");
			index++;
		}
		strcpy(&(submission[index]), temp->color);
		index=index+strlen(temp->color);
	}
	strcat(submission, "\n");
	write(sockfd, submission, strlen(submission));
	read(sockfd,buffer,BUFFERSIZE);
	*reds=atoi(buffer);
	index=0;
	len=strlen(buffer);
	while(buffer[index]!=',' && index<len){
		index++;
	}
	index++;
	*whites=atoi(&(buffer[index]));
	guesses++;
//	printf("Code: %s",submission);
//	printf("Reds: %d\nWhites: %d\n\n",*reds, *whites);
}

void initialRandom(){
	int reds=0;
	int whites=0;
	int i;
	int guess[numPins];
	for(i=0; i<numPins; i++){
		guess[i]=random()%numColors;
	}
	submitGuess(guess, &whites, &reds);
	addEntry(guess, whites, reds);
	for(i=0; i<numPins; i++){
		guess[i]=random()%numColors;
	}
	while(findEntry(guess)){
		for(i=0; i<numPins; i++){
			guess[i]=random()%numColors;
		}
	}
	submitGuess(guess, &whites, &reds);
	addEntry(guess, whites, reds);
}

void initialGuesses(){
	int reds=0;
	int whites=0;
	int color=0;
	int done=0;
	int i;
	int guess[numPins];
	while(color<numColors){
		for(i=0; i<numPins/2+numPins%2; i++){
			guess[i]=color;
		}
		color++;
		if(color>=numColors){
			color=0;
		}
		for(i; i<numPins; i++){
			guess[i]=color;
		}
		submitGuess(guess, &whites, &reds);
		addEntry(guess, whites, reds);
		if(reds==numPins){
			printf("found the solution in %d guesses\n",totalEntries);
			exit(0);
		}
		if(color==0){
			break;
		}
		color++;
	}
	color=0;
	while(color<numColors && !done){
		for(i=0; i<numPins; i++){
			guess[i]=color;
			color++;
			if(color>=numColors){
				color=0;
				done=1;
			}
		}
		submitGuess(guess, &whites, &reds);
		addEntry(guess, whites, reds);
	}
}

void crossover(Entry* parentA, Entry* parentB, int code[]){
	int parentPins = (parentA->whites + parentA->reds) + (parentB->whites + parentB->reds) + 2;
	int parentAPins = (parentA->whites + parentA->reds) + 1;
	int parentBPins = (parentB->whites + parentB->reds) + 1;
	int i;
	for(i = 0; i < numPins; i++){
		int rnd = random() % parentPins;
		if(parentAPins >= rnd){
			code[i] = parentA->code[i];
		}
		else{
			code[i] = parentB->code[i];
		}
	}
}

void mutate(int code[]){
	int i;
	for(i=0; i<numPins; i++){
		if(random() % (numPins * 100) < MUTATIONRATE){
			code[i] = random() % numColors;
		}
	}
}

void geneticGuess(){
	int parentAIndex = 0;
	int parentBIndex = 0;
	int redPins = 0;
	int whitePins = 0;
	int oldTime = time(NULL);
	while(redPins != numPins){
		/*random() % range + startingAt*/
		if((time(NULL) - oldTime) > 2){
			srandom(time(NULL));
			oldTime = time(NULL);
		}
		if(totalEntries < 20){
			parentAIndex = random() % totalEntries;
			parentBIndex = random() % totalEntries;
			while(parentAIndex == parentBIndex){
				parentBIndex = random() % totalEntries;
			}
		}
		else if(totalEntries<60){
			int range = (int)(.05 * totalEntries);
			if(range < 5){
				range = 5;
			}
			parentAIndex = random() % range;
			parentBIndex = random() % (range * 2);
			while(parentAIndex == parentBIndex){
				parentBIndex = random() % (range * 2);
			}
		}
		else if(totalEntries<500){
			int range = (int)(.02 * totalEntries);
			if(range < 5){
				range = 5;
			}
			parentAIndex = random() % range;
			parentBIndex = random() % (range * 2);
			while(parentAIndex == parentBIndex){
				parentBIndex = random() % (range * 2);
			}
		}
		else{
			int range = (int)(.01 * 500);
			if(range < 5){
				range = 5;
			}
			parentAIndex = random() % range;
			parentBIndex = random() % (range * 2);
			while(parentAIndex == parentBIndex){
				parentBIndex = random() % (range * 2);
			}
		}
		Entry *parentA = primaryEntry;
		int i = 0;
		for(i = 0; i < parentAIndex; i++){
			parentA = parentA->next;
		}
		Entry *parentB = primaryEntry;
		for(i = 0; i < parentBIndex; i++){
			parentB = parentB->next;
		}
		int code[numPins];
		crossover(parentA, parentB, code);
		mutate(code);
		if(findEntry(code) == 0){
			submitGuess(code, &whitePins, &redPins);
			addEntry(code, whitePins, redPins);
		}
		
	}
	
}

int main(int argc, char *argv[]){
	int reds=0;
	int whites=0;
	if(argc<3){
		exit(1);
	}
	srandom(time(NULL));
	initialize(argv[1], argv[2]);
	initialGuesses();
	geneticGuess();
}